package alogrithm.solution;

/*
 * 第14题：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
 */
public class P14 {
	public static void getPair(int sum,int sortedArray[])
	{
		if(sortedArray==null)return;
		int i=0,j=sortedArray.length-1;
		while(i<j)
		{
			if(sortedArray[i]+sortedArray[j]==sum)
			{
				System.out.println(sortedArray[i]+"\t"+sortedArray[j]);
				break;
			}
			else if(sortedArray[i]+sortedArray[j]>sum)
				j--;
			else i++;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[]={1,2,5,7,8,9};
		getPair(9,array);

	}

}
